The present invention pertains generally to the field of packet data networks and, more particularly, to system architectures and methods for regulating and managing the flow of data packets in a packet data router.
In a typical packet data router, packets originating from various source locations are received via a plurality of communication interfaces. Each packet contains routing information, such as a destination address, which is associated with a respective communication interface of the router, e.g., by a routing table or packet forwarding protocol. The router reads the routing information of each received packet and, if it recognizes the information, forwards the packet to the appropriate communication interface for further transmission to its destination. Packets without known destination address or forwarding protocol information are typically dropped.
Due to normal ebbs and flows in packet data traffic patterns and volume, a packet data router may be unable to immediately route newly received packets to respective designated communication interfaces. In particular, packet data traffic tends to have bursts of high activity, which is followed by lulls. Thus, a packet data router may be characterized as having a sustained data rate and a burst data rate. When receiving a burst of packet traffic, the router will temporarily store the received packets in an associated memory until t has the processing capacity available to process and forward the packets to their respective outgoing communication interface. When the sustained or burst data rates of a router are exceeded for a certain period of time, it is inevitable that further incoming packets will be dropped. Of course, while sometimes unavoidable, dropping unprocessed packets is undesirable because the source will then retransmit the dropped packet as part of its recovery procedure, which tends to prolong the congested state of the packet router and cause further unprocessed packets to be dropped.
Packet data network users often share either a single router, or router system, from a service provider. Multiple different internet users, for example, may connect via respective data modems or primary rate interface (xe2x80x9cPRIxe2x80x9d) lines to a single internet protocol (xe2x80x9cIPxe2x80x9d) router, or IP router system, operated by an internet service provider (xe2x80x9cISPxe2x80x9d). These end users may be single customers themselves, or there may be multiple (e.g., networked) users combined as a single customer account by the ISP. Each customer account may be allocated a respective level of service priority and packet throughput bandwidth by the ISP, depending on the type and level of service connectivity that is contracted for.
For purposes of clarification, as referred to herein, a xe2x80x9crouterxe2x80x9d is defined as a physical (as opposed to logical) entity having a defined number of physical communication interfaces (e.g., modems) under the control of one or more processors collectively executing a single control function. Typically, a single physical router operates under a single routing domainxe2x80x94i.e., wherein a packet received on any communication interface may be forwarded only to the same, or any other communication interface of the router. As referred to herein, a xe2x80x9crouter systemxe2x80x9d is defined as two or more independent routers, with an external controller for selectively directing common (incoming) packet data traffic to respective routers within the system.
It is known to implement within a single router one or more virtual router instances (xe2x80x9cVRIsxe2x80x9d). Each VRI has its own subset of communication interfaces, or logical circuits on a shared communication interface, and its own routing domain, but still under the control of a common control function with the other packet traffic handled by the router. In particular, a VRI exists as a collection of processes performed by the router, which correspond roughly to the layers in the TCP/IP protocol model. For example, a private network can be configured as a VRI, so that packet data may only be exchanged between end users on the same network. It has also been proposed to have a single VRI span multiple routers in a router system. For example, one suggested implementation is to have a dedicated interface link bridging respective communication interfaces of multiple routers having a common VRI.
Because of varying and often unpredictable growth rates, as well as other economic factors, a packet router, or packet router system, will not necessarily have the processing or memory capacity to simultaneously provide the contracted for bandwidth allocation for every user or VRI it services. Further, various users will connect to the IP router at different, often unpredictable, times and with varying rates and bandwidth needs.
An IP router is typically controlled with a real time operating system (xe2x80x9cRTOSxe2x80x9d), which allows multiple processes of different priorities to co-exist under the control of a common control function (e.g., within a single central processing unit). For example, the RTOS may have sensors that provide feedback information regarding current usage characteristics for a given user, which is used to adjust the RTOS operating parameters in response to changes in demand. Common applications for the RTOS are process control, motion control and, in certain applications, command and control.
The problem is that these operating systems often fail to effectively accommodate the different priority and bandwidth requirements contracted for by the end user customers of the ISP. In a motion control system, for example, the flow of information from sensors is into the system, and the flow of control signals is out of the system. There may be a lot of sensors, and there may be a lot of subsystems being controlled, but the input information does not circulate through the system and become the output. This has the effect of making the inherent control feature of the RTOS process/task priority ineffectual for controlling the system.
A typical IP router is a xe2x80x9cpacket drivenxe2x80x9d system. The more data packet it receives, the greater the load, and that load traverses the whole system such that the input is (for all practical purposes) the output. Thus, users whose connection to the router is handling the most packets will tend to monopolize the system resources.
For example, consider a router that is divided into two different VRIs, with each VRI having roughly the same number of end users and paying an ISP for the same quality of service (xe2x80x9cQOSxe2x80x9d), including identical priority and bandwidth requirements. Thus, the router should be able to provide the end users of each VRI with the same number of bits-per-second (xe2x80x9cBPSxe2x80x9d) system throughput at any given time. Suppose, however, that the router processing capability is barely adequate to handle the peak load of even one of the VRIs without dropping unprocessed packets. If users of the first VRI have, in effect, tied up the router throughput processing capabilities, the users of the second VRI will not receive the service priority and bandwidth they are otherwise entitled to.
Thus, there is a need for methods and system architectures for more fairly regulating the processing of data packets through a packet data router, or router system, whereby the quality of service is balanced for each user and/or VRI, and wherein the system is kept stable, even when heavy loads occur.
In accordance with a first aspect of the invention, a method is provided for controlling the processing of data packets in a packet data router by dynamically adjusting the rate at which packets held in a respective ingress data queue are processed based on current operating conditions of the router.
In a preferred embodiment, the ingress data queue has a data queue head structure including a packets-to-be-processed field and a sustained-data-rate field. The packets-to-be-processed field stores a value indicating a number of packets held in the ingress data queue that are to be processed by the router during a given processing interval. In this manner, the packet flow rate of the ingress data queue may be adjusted by increasing or decreasing the value of the packets-to-be-processed field based on current operating conditions of the router, such as, e.g., such as processor or memory utilization. The sustained-data-rate field stores a value indicating a target (e.g., maximum) data processing rate, in bits-per-second, for the ingress data queue. The value of the packets-to-be-processed field is normally based on the sustained-data-rate of the ingress data queue.
In accordance with a further aspect of the invention, a method of dynamically adjusting the packet flow rate of an ingress data queue includes detecting whether a burst of data packets has been (or is being) received on the queue. In a preferred embodiment, the data queue head structure includes both a burst-data-rate field and a burst-duration field. The burst-data-rate field stores a value indicating a selected rate for processing data packets held in the ingress data queue if a received burst of data packets has been detectedxe2x80x94i.e., which is greater than the sustained-data rate. When a data burst is detected, the packets-to-be-processed field is recalculated based on the burst-data-rate, instead of the sustained-data-rate. The burst-duration field stores a value indicating a time period for sustaining the processing rate of the ingress data queue based on the burst-data-rate. In this manner, the packet flow rate of the ingress data queue may be further controlled by increasing or decreasing the values of the burst-data-rate field or of the burst-duration field.
In accordance with a still further aspect of the invention, the data queue head structure of an ingress data queue is also provided with a queue-depth field, which stores a value indicating the current amount of router memory allocated to store data packets in the ingress data queue. Once this limit is reached, any further packets directed to the ingress data queue will be dropped. Depending on current operating conditions of the router, the queue-depth field may be increased or decreased in order to adjust the memory utilization of the routerxe2x80x94i.e., by limiting the number of packets that may be held in the router memory for processing at any given interval.
In accordance with a yet another aspect of the invention, a method is provided for controlling the processing of data packets in a packet data router by dynamically adjusting the rate at which packets held in a plurality of ingress data queues are processed based on current operating conditions of the router.
In a preferred embodiment, the packet flow rate of each ingress data queue is adjusted independently of the packet flow of the other ingress data queues, thereby allowing for flexible management and control on an ingress data queue level. The method preferably also includes detecting whether a burst of data has been received on at least one of the plurality of ingress data queues. For example, the packet-flow rate of a first ingress data queue may be increased, while simultaneously decreasing the packet flow rate of a second ingress data queue, in order to accommodate processing of a burst of packets received on the first queue without jeopardizing the overall system throughput and operational stability of the router.
In accordance with a still further aspect of the invention, the data queue head structure of each of a plurality of ingress data queues is provided with a queue-depth field, which stores a value indicating the current amount of memory allocated to store data packets in the respective ingress data queue. In a preferred embodiment, the queue-depth fields of each ingress data queue are independently increased or decreased in order to control memory utilizationxe2x80x94i.e., by limiting the number of packets that may be held in the router memory for processing at any given interval on any given ingress data queue. In a preferred embodiment, memory utilization is also be controlled by adjusting the packet flow rate(s) of one or more ingress data queue(s).
As will be apparent to those skilled in the art, other and further aspects and advantages of the present invention will appear hereinafter.